//把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2
//] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。 
//
// 示例 1： 
//
// 输入：[3,4,5,1,2]
//输出：1
// 
//
// 示例 2： 
//
// 输入：[2,2,2,0,1]
//输出：0
// 
//
// 注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sor
//ted-array-ii/ 
// Related Topics 二分查找 
// 👍 124 👎 0

package leetcode.editor.cn;
//Java：旋转数组的最小数字
public class PJzOffer11XuanZhuanShuZuDeZuiXiaoShuZiLcof{
    public static void main(String[] args) {
        Solution solution = new PJzOffer11XuanZhuanShuZuDeZuiXiaoShuZiLcof().new Solution();
        // TO TEST
        int[] nums={2,2,2,0,1};
        int res=solution.minArray(nums);
        System.out.println(res);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        public int minArray(int[] numbers) {
        /*
        1 2 3 4 5
        3 4 5 2 1
        0 1 1 1 1
        1 1 1 0 1
        */

            int begin=0,end=numbers.length-1;
            if(numbers[begin]<numbers[end]){//严格递增
                return numbers[begin];
            }

            int mid=0;
            while(numbers[begin]>=numbers[end]){
                if(end-begin==1){
                    mid=end;
                    break;
                }
                mid=begin+(end-begin)/2;
                if(numbers[begin]==numbers[mid]&&numbers[mid]==numbers[end]){
                    return getMin(numbers,begin,end);
                }

                if(numbers[mid]>=numbers[begin]){//位于左半部分，去右边找
                    begin=mid;//此处不能+1，因为会把这个数字排除掉
                }
                if(numbers[mid]<=numbers[end]){
                    end=mid;
                }

            }

            return numbers[mid];
        }

        public int getMin(int[] numbers,int begin,int end){
            if(begin>end){
                return -1;
            }
            int min=numbers[begin];
            for(int i=begin+1;i<=end;i++){
                if(numbers[i]<min){
                    min=numbers[i];
                }
            }
            return min;
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}
